package BFS;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-08
 * Time:21:39
 * Text：200. 岛屿数量
 */
public class Text2 {
    int[] dx={0,0,-1,1};
    int[] dy={1,-1,0,0};
    boolean[][] vis = new boolean[301][301];
    int m,n;
    /*
    * 不改变原数组
    * */
    public  int numIslands(char[][] grid) {
        m = grid.length; n = grid[0].length;
        int ret = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0;j < n; j++)
            {
                if(grid[i][j] == '1' && !vis[i][j])
                {
                    ret++;
                    bfs(grid, i, j);
                }
            }
        }
        return ret;
    }
    public void bfs(char[][] grid, int i, int j)
    {
        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{i,j});
        vis[i][j] = true;
        while(!q.isEmpty())
        {
            int[] t=q.poll();
            int a = t[0],b=t[1];
            for(int k=0;k<4;k++)
            {
                int x=a + dx[k], y=b+ dy[k];
                if(x >= 0 && x< m && y>=0 && y<n && grid[x][y]=='1' && !vis[x][y])
                {
                    q.add(new int[]{x,y});
                    vis[x][y] = true;
                }
            }
        }
    }
    /*
    * 改变原数组
    * */
    public  int numIslands2(char[][] grid) {
        Queue<int[]> q=new LinkedList<>();
        int ret=0;
        //遍历grid数组,如果碰见char[][] grid为1时，开始进行循环将符合条件的数组
        for(int i = 0 ; i < grid.length ; i++)
        {
            for(int k=0; k < grid[0].length; k++)
            {
                //开始循环
                if(grid[i][k] == '1'){
                    //把下标存放在队列里
                    q.add(new int[]{i,k});
                    while(!q.isEmpty())
                    {
                        int[] t = q.poll();
                        int x = t[0],y = t[1];

                        for(int y2 = 0 ; y2 < 4; y2++){
                            int x1 = x + dx[y2],y1 = y + dy[y2];
                            if(x1>=0 && x1<grid.length && y1>=0 && y1<grid[0].length && grid[x1][y1]== '1')
                            {
                                q.add(new int[]{x1,y1});
                                grid[x1][y1] = '0';
                            }
                        }
                    }
                    ret++;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Text2 t1=new Text2();
        char[][] c= {{'1','1','1','1','1','0','1','1','1','1','1','1','1','1','1','0','1','0','1','1'},
                {'0','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','0'},
                {'1','0','1','1','1','0','0','1','1','0','1','1','1','1','1','1','1','1','1','1'},
                {'1','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
                {'1','0','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
                {'1','0','1','1','1','1','1','1','0','1','1','1','0','1','1','1','0','1','1','1'},
                {'0','1','1','1','1','1','1','1','1','1','1','1','0','1','1','0','1','1','1','1'},
                {'1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','0','1','1'},
                {'1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1'},
                {'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
                {'0','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1'},
                {'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
                {'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
                {'1','1','1','1','1','0','1','1','1','1','1','1','1','0','1','1','1','1','1','1'},
                {'1','0','1','1','1','1','1','0','1','1','1','0','1','1','1','1','0','1','1','1'},
                {'1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','0'},
                {'1','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','0','0'},
                {'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
                {'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},
                 {'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'}};
        System.out.println(t1.numIslands2(c));

    }
}
